/**
 * @file minimum_spanning_tree.cpp
 * @author your name (you@domain.com)
 * @brief 最小生成树问题
 * @version 0.1
 * @date 2022-01-05
 *
 * @copyright Copyright (c) 2022
 *
 */
#include <bits/stdc++.h>
/**
 * @brief 使用Prim解决最小生成树问题
 *
 * @param matrix
 * @param destination
 * @return std::pair<int32_t, std::vector<int32_t>>
 */
std::pair<int32_t, std::vector<int32_t>> Prim(
    std::vector<std::vector<int32_t>>& matrix, int32_t origin = 0) {
  int32_t num_vertexes = matrix.size();
  std::vector<int32_t> path;  // 记录最小生成树路径
  path.emplace_back(origin);

  std::vector<int32_t> distance(num_vertexes, INT16_MAX);
  // distace[i] 表示顶点 i 到 起点的距离

  std::bitset<100> visited(0);  //标记是否已经被加入生成树

  int32_t sum_distance{0};

  //初始化
  for (int32_t v_id = 0; v_id < num_vertexes; v_id++) {
    distance[v_id] = matrix.at(origin).at(v_id);
    //初始化为origin 到其他各个顶点的距离
  }

  //开始进行
  while (path.size() <= num_vertexes) {
    int32_t next_vertex = (origin + 1) % num_vertexes;  // 记录下一个顶点

    // 寻找距离已经形成的最小生成树距离最近的点
    int32_t minimum_distance = INT16_MAX;
    for (int32_t v_id = next_vertex; v_id < num_vertexes; v_id++) {
      if (!visited[v_id] && distance.at(v_id) < minimum_distance) {
        minimum_distance = distance.at(v_id);
        next_vertex = v_id;
        path.emplace_back(next_vertex);  // 添加到路径上
      }
    }
    sum_distance += minimum_distance;
    visited[next_vertex] = 1;  //标记为已经访问过

    for (int32_t v_id = 0; v_id < num_vertexes; v_id++) {
      if (!visited[v_id] &&
          matrix.at(next_vertex).at(v_id) < distance.at(v_id)) {
        distance.at(v_id) = matrix.at(next_vertex).at(v_id);
      }
    }
  }

  return {sum_distance, path};
}

struct Edge {
  int32_t v_begin;
  int32_t v_end;
  int32_t weight;
  Edge(int32_t begin, int32_t end, int32_t w)
      : v_begin(begin), v_end(end), weight(w){};
  bool operator<(const Edge& e) const { return weight < e.weight; }
};
std::pair<int32_t, std::vector<Edge>> Kruskal(std::vector<Edge>& Graph) {
  int num_edge = Graph.size();
  std::vector<int32_t> parent(num_edge, 0);
  for (auto i = 0; i < parent.size(); i++) {
    parent.at(i) = i;  //每个顶点的自己形成一个集合
  }
  std::vector<Edge> path;  // 记录路径
  int64_t sum_of_path{0};  //计算路径总和

  auto find = [&parent](int x) -> int32_t {
    while (parent.at(x) != x) {
      x = parent.at(x);
    }
    return parent.at(x);
  };
  for (int32_t e_id = 0; e_id < num_edge; e_id++) {
    Edge cur_edge = Graph.at(e_id);
    int32_t begin_vertex_parent = find(cur_edge.v_begin);
    int32_t end_vertex_parent = find(cur_edge.v_end);

    if (begin_vertex_parent != end_vertex_parent) {
      parent.at(begin_vertex_parent) = end_vertex_parent;  // 和并集合
      path.emplace_back(cur_edge);
      sum_of_path += cur_edge.weight;
    }
  }

  return {sum_of_path, path};
}